package Leetcode;
import java.util.*;

/* 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

class Solution {		//dp动态规划
    public int minCostClimbingStairs(int[] cost) {		//因为一定要到达顶部，而且可以从0,1开始，所以遍历下标2到终点的数组，维护三个数字作为起点1，起点2，体力最小值
    	int n = cost.length;		//得到数组长度
    	int index1 = 0,index2 = 0;		//维护起点1和2
    	for(int i=2;i<=n;i++) {		//遍历数组，从要跳的位置开始（即第三个位置，下标为2）
    		int min = Math.min(index1+cost[i-2],index2+cost[i-1]);		//维护一个消耗最小体力值，比较从起点1或者起点2起跳消耗的体力
    		index1 = index2;	//比较完后，将起点1和2更新，起点1为刚才起点2的位置
    		index2 = min;		//起点2为刚才跳的终点位置
    	}
    	return index2;		//到循环结束时，起点2即终点
    }
}

public class LeetCode746 {
	public static void main(String [] args) {
		
	}
}
